#include "Trie.h"

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// 创建一个新的Trie节点
TrieNode *trie_create_node(void *data) {
    TrieNode *node    = (TrieNode *) malloc(sizeof(TrieNode));
    node->data        = data;
    node->isEndOfWord = 0;
    node->isWildcard  = 0; // 默认不是通配符节点

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }

    return node;
}

// 插入一个单词到Trie中
void trie_insert(TrieNode *root, const char *key, void *data) {
    TrieNode *pCrawl = root;
    int       level  = 0;
    while (key[level] != '\0') {
        if (key[level] == '/' && key[level + 1] == '*' && key[level + 2] == '*') {
            // 如果是 /**，我们将该节点标记为通配符节点
            if (!pCrawl->isWildcard) {
                pCrawl->isWildcard = 1;
                break; // 插入一个通配符节点后就停止，因为 /** 匹配任意后续路径
            }
        }

        int index = CHAR_TO_INDEX(key[level]);
        if (pCrawl->children[index] == NULL) {
            pCrawl->children[index] = trie_create_node(data);
        }

        pCrawl = pCrawl->children[index];
        level++;
    }

    pCrawl->isEndOfWord = 1;
}

// 在Trie中搜索一个单词
void *trie_search(TrieNode *root, const char *key) {
    TrieNode *pCrawl = root;
    int       level  = 0;
    while (key[level] != '\0') {
        int index = CHAR_TO_INDEX(key[level]);

        if (pCrawl->isWildcard) {
            // 如果当前节点是通配符节点，继续匹配后续路径
            return pCrawl->data;
        }

        if (pCrawl->children[index] == NULL) {
            return NULL;
        }

        pCrawl = pCrawl->children[index];
        level++;
    }

    if (pCrawl != NULL && pCrawl->isEndOfWord) {
        return pCrawl->data;
    }

    return NULL;
}

// 检查Trie中是否存在具有指定前缀的路径
void *trie_starts_with_prefix(TrieNode *root, const char *prefix) {
    TrieNode *pCrawl = root;
    int       level  = 0;
    while (prefix[level] != '\0') {
        int index = CHAR_TO_INDEX(prefix[level]);

        if (pCrawl->isWildcard) {
            // 如果是通配符节点，匹配成功
            return pCrawl->data;
        }

        if (pCrawl->children[index] == NULL) {
            return NULL;
        }

        pCrawl = pCrawl->children[index];
        level++;
    }

    return pCrawl->data;
}